package com.cet.algorithm.二叉树.对称二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm
 * @description: 另一棵树的子树
 * @author: 陈恩涛
 * @create: 2022-07-19 15:58
 **/
public class LC572 {

    int max = Integer.MIN_VALUE;
    int lNull;
    int rNull;

    public static void main(String[] args) {
        final TreeNode root = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2, new TreeNode(0), null)), new TreeNode(5));
        final TreeNode subRoot = new TreeNode(4, new TreeNode(1), new TreeNode(2));
        System.out.println(new LC572().isSubtree(root, subRoot));
    }

    /**
     * kmp法
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        getMaxValue(root);
        getMaxValue(subRoot);
        lNull = max + 1;
        rNull = max + 2;
        List<Integer> tOrder = new ArrayList<>();
        List<Integer> sOrder = new ArrayList<>();
        preorderTraversal(root, tOrder);
        preorderTraversal(subRoot, sOrder);
        return kmp(tOrder, sOrder) != -1;
    }

    private void getMaxValue(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.val > max) {
            max = root.val;
        }
        getMaxValue(root.left);
        getMaxValue(root.right);
    }

    private void preorderTraversal(TreeNode root,List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        if (root.left != null) {
            preorderTraversal(root.left, list);
        } else {
            list.add(lNull);
        }

        if (root.right != null) {
            preorderTraversal(root.right, list);
        } else {
            list.add(rNull);
        }
    }

    /**
     * 生成next数组
     * @param next next数组
     * @param preorderList 带扫描序列
     */
    private void getNext(int[] next, List<Integer> preorderList) {
        // j指向前缀末尾
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < preorderList.size(); i++) {
            while (j > 0 && !preorderList.get(j).equals(preorderList.get(i))) {
                j = next[j - 1];
            }
            if (preorderList.get(j).equals(preorderList.get(i))) {
                j++;
            }
            next[i] = j;
        }
    }

    private int kmp(List<Integer> tOrder, List<Integer> sOrder) {
        if (sOrder.size() == 0) {
            return 0;
        }
        int[] next = new int[sOrder.size()];
        getNext(next, sOrder);
        int j = 0;
        for (int i = 0; i < tOrder.size(); i++) {
            while (j > 0 && !tOrder.get(i).equals(sOrder.get(j))) {
                j = next[j - 1];
            }
            if (tOrder.get(i).equals(sOrder.get(j))) {
                j++;
            }
            if (j == sOrder.size()) {
                return i - j + 1;
            }
        }
        return -1;
    }
}
